%

\documentclass[11pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\F}{{\mathbb{F}}}
%\usepackage{psfig}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{fullpage, color}

\usepackage{epsfig,graphicx, multirow,pdfpages}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}

\input{preamble.tex}

%{lecture number}{lecture date}{Elena Grigorescu}{Your name}
\lecture{7}{Sep 11, 2012}{Elena Grigorescu}{Greg Hurst}

%%%% body goes in here %%%%


\noindent {\Large \bf Today:}
\begin{itemize}
\item We'll show how the $\triangle$-removal lemma (proved in the previous lecture) implies Roth's theorem.
\item We'll show a lower bound on testing $\triangle$-freeness, due to \cite{alon02}.
\end{itemize}

First recall the $\triangle$-removal lemma.

\begin{lemma}

For all $\epsilon > 0$ there exists $\delta(\epsilon) > 0$ such that every graph $G$ on $n$ vertices which is $\epsilon$-far from $\triangle$-free contains $\delta \binom n3 $ $\triangle$'s.

\end{lemma}

\noindent Recall that $\epsilon$-far means we need to remove $\epsilon \binom n2$ edges to remove all $\triangle$'s from $G$.

\begin{definition}

A {\em length-3-arithmetic progression} (or 3-AP) is a triple $\{x, x+\alpha, x+2\alpha\}$ for $x,\alpha\in\Z,$ or equivalently, a tuple $\{a, b, c\}$ s.t. $a+c=2b$, $a, b, c\in \Z$. The 3-AP is called 
{\em trivial} if $\alpha=0$ (or equivalently, $a=b=c$), and it is called {\em non-trivial} otherwise. 


\end{definition}

\noindent A question well-studied in the area of additive combinatorics is the following: what is the size of the largest set  $S \subset [n] = \{1, 2, \ldots, n\}$ that does not contain any 3-AP?

An example of such $S\subset[10]$ is $\{1,2,4,5,10\}$.


In this lecture we describe some known upper and lower bounds for $S$, namely

\begin{itemize}
\item upper bound on $S$: any $S$ with $|S|>\delta n$ must contain a 3-AP (Roth's theorem)
\item lower bound on $S$: there exists $S$ with $|S| =  \displaystyle\frac n{2^{c \sqrt{ \log n}}}=\Omega(n^{1-\epsilon})$ that does not contain any 3-AP.(Behrend's theorem). We note that this result was shown in the 40's and has only recently been improved \cite{Elk10}.
\end{itemize}

\begin{figure}[h!]
\includegraphics[scale=1.5]{n1.pdf}
\end{figure}


\begin{theorem}[Roth]
For all $\epsilon>0$ there exists $n_0(\epsilon) > 0$ such that for all $n > n_0(\epsilon)$, any $A\subset[n]$ with $|A| > \epsilon n$ must contain a 3-AP.
\end{theorem}

\begin{proof}

\noindent Construct a graph $G = (V = V_1\sqcup V_2\sqcup V_3, E)$ where $V_1$ has $n$ vertices, $V_2$ has $2n$ vertices, $V_3$ has $3n$ vertices, and has edges that satisfy exactly one of the following:
 \begin{itemize}
 \item for $u\in V_1$ and $v\in V_2$, add edge $(u,v)$ is there is an $a\in A$ such that $v = u+a$
 \item for $v\in V_2$ and $w\in V_3$, add edge $(v,w)$ is there is an $c\in A$ such that $w = v+c$
 \item for $u\in V_1$ and $w\in V_3$, add edge $(u,w)$ is there is an $b\in A$ such that $w = u+2b$
 \end{itemize}
 
 \includegraphics[scale=1.5]{g1.eps}\\

 \noindent For $G$ we get $|V| = 6n$ and $|E| = n|A| + 2n|A| + n|A| = 4n|A|$.\\
 
 \noindent Now every $\triangle$ in $G$ corresponds to a 3-AP in $A$ since $u+2b = w = v+c = u+a+c \implies 2b = a+c$. This means $$\# \triangle \text{'s in }G = n\cdot (\# \text{non-trivial 3-AP's} + \# \text{trivial 3-AP}\triangle\text{'s}) = n\cdot(\# \text{non-trivial 3-AP's}+|A|).$$

\noindent Also $$\# \text{edge disjoint }\triangle\text{'s} \geq |\{(x, x+a, x+2a) \mid x\in[n], a\in A\}| =n|A| \geq \epsilon n^2.$$
 Since we need to remove at least one edge from the edge-disjoint triangles in order to distroy all the $\triangle$'s in $G$, this implies that $$\text{dist}(G, \triangle\text{-freeness}) \geq \frac{\# \text{edge disjoint }\triangle\text{'s}}{\binom n2} \geq \frac \epsilon4$$ and so by the $\triangle$-removal lemma, $G$ has at least $\delta(\epsilon)n^3$ many triangles.\\

\noindent From here we conclude $\displaystyle n\cdot( \# \text{non-trivial 3-AP's}+|A|) \geq \delta n^3 \implies \# \text{non-trivial 3-AP's} > \delta n^2 - |A| > \delta n^2 - n \gg 1$.

\end{proof}

\newpage

\begin{theorem}[Behrend]
There exists $A\subset[n]$ of size $\displaystyle \frac n{2^{c\sqrt{\log{n}}}}$ such that $A$ has no 3-AP.
\end{theorem}

We won't show this theorem here but we will show a nice connection to property testing, namely we will show how it implies a lower bound on the query complexity of tests for $\triangle$-freeness.

\begin{theorem}[Lower bound for testing $\triangle$-freeness]\label{tri-free}
For all $\epsilon > 0$ there exists a graph $G$ on $n$ vertices such that any one sided error test must make $\displaystyle\Omega\left(\left(\frac c\epsilon\right)^{c \log{(c/\epsilon)}}\right)$ queries.
\end{theorem}

The lower bound is shown by exhibiting a graph that is far from being $\triangle$-free yet does not have that many triangles (but it still has a constant fraction of the total number of triangles possible). In particular, the inverse of the fraction of triangles is superpolynomial in $\frac{1}{\epsilon}$, but much much smaller than the tower of exponentials upper bound from the triangle removal lemma (which in turn comes from the constant in Szemeredi's regularity lemma).

\begin{theorem}[Alon \cite{alon02}]\label{alon}
There exists $c>0$ such that for all $\epsilon > 0$ and $n > n_0(\epsilon)$ there exists a graph $G$ on $n$ vertices such that $G$ is $\epsilon$-far from $\triangle$-free and $G$ contains at most $\displaystyle\left(\frac \epsilon c\right)^{c \log{(c/\epsilon)}}\cdot \binom{n}{3}$ triangles..
\end{theorem}


\includegraphics[scale=1.5]{n2.pdf}\\

\begin{proof}[of Theorem \ref{tri-free}]
Let $G$ be the graph given by Theorem \ref{alon}.

As we've seen before, one possible test could be:  pick three vertices uniformly at random and check if they form a $\triangle$. If so reject. Then it follows that $$P[\text{rej }G] =\frac{\#\triangle' s}{\binom{n}{3}}\leq \displaystyle\left(\frac \epsilon c\right)^{c \log{(c/\epsilon)}}.$$

Therefore, in order to reject $G$ w.p. $2/3$ we need to repeat this test  at least $ \displaystyle\frac1 {100}\left(\frac \epsilon c\right)^{c \log{(c/\epsilon)}}$ many times.


Note that this does not complete the proof of the theorem sice we only analyzed one possible test, while the theorem states that any test must have this query complexity. Notice that the test above was non-adaptive and it only operated by checking the existence of triangles. One can imagine more interesting  adaptive tests that might not need as many queries.
 
 It turns out that in fact any (single sided) test (even fancy adaptive ones) can be reduced to the test above which simply picks a few vertices and  makes a decision based on querying the edges spanned by these vertices. Importantly, the query complexity only blows up quadratically. We next state the formal  theorem due to Goldreich and Trevisan \cite{GT03} describing this result.



\begin{theorem}\label{gt}
If $T$ is a test (possibly adaptive) for a graph property $P$ that makes $q=q(\epsilon, n)$ queries then there exists a test $T'$ that, on input a graph $G$, picks $2q$ uniformly random vertices and accepts/rejects based on queries on the edges spanned by these vertices. The query complexity of $T'$ is thus $2q^2$. Moreover, if $T$ is single-sided so is $T'$. Such a test is called a {\em canonical test}. 
\end{theorem}

So the test shown above is a canonical test for $\triangle$-freeness. 
Therefore, to finish the proof of the lower bound for triangle freeness, note that if there existed a test with query complexity $q=o\left(\left(\frac c\epsilon\right)^{c \log{(c/\epsilon)}}\right)=\left(\frac c\epsilon\right)^{ o( \log{(1/\epsilon)})}$, then there would exist a  canonical test with query complexity $q^2=\left(\frac c\epsilon\right)^{2\cdot o( \log{(1/\epsilon)})}$, a contradiction to the lower bound shown above for the canonical test.

\end{proof}


\begin{proof}{\bf\!\!\!of Theorem \ref{alon}}

\noindent Consider the graph $G=G(V, E(G))$ from the proof of Roth's theorem, where the set $A\in [n]$ is this time the set given by Behrend's theorem.\\
 For this proof we will switch the letter $n$ (the number of vertices) for the letter $m$.\\
 \;\\

 Recalling facts from before, we have
 \begin{enumerate}
 \item $|A| = \displaystyle \frac m{2^{c\sqrt{\log{m}}}}$
 \item  $|V| = 6m$, 
 \item $|E| = 4m|A|$,
 \item $\# \text{edge disjoint }\triangle\text{'s}= m|A|$, (since $A$ is triangle free, so the only possible triangles in $G$ are those of the form $\{x, x+a, x+2a\}$, with $x\in [m]$ and $a\in A$.
 \item $\text{dist}(G, \triangle\text{-freeness}) \geq \frac{m|A|}{\binom m2} \geq \frac1{36}\frac{|A|}m.$
\end{enumerate}
We want $G$ to be $\epsilon$-far from $\triangle$-free, so we want $m$ s.t. $ \frac1{36}\frac{|A|}m > \epsilon$. 

 So choose $m$ such that $$\left \lfloor \frac1{36}\frac{|A|}m \right \rfloor - 1 \leq m < \left \lfloor \frac1{36}\frac{|A|}m \right \rfloor \implies m = \Theta\left(2^{\log^2{(c'/\epsilon)}}\right) = \Theta\left(\left(\frac {c'}{\epsilon} \right)^{c' \log{(c'/\epsilon)}}\right),$$
for a suitable constant $c'$ (independent of $\epsilon$).
 
 Now construct a graph $G'$ from $G$ as follows:
 \begin{itemize}
 \item for each $v\in G$, replace $v$ with $s = \Theta\left(\frac nm\right)$ vertices
 \item replace each edge with a complete bipartite graph (with $s$ vertices on the left and $s$ vertices on the right).
 \end{itemize}
 
 \includegraphics[scale=1.5]{g2.eps}\\

 \noindent For $G'$ we get 
 \begin{enumerate}
 \item $|V(G')| = 6ms=n$, 
 \item $|E(G')| = 4m|A|s^2$,
 \item $\# \triangle\text{'s} = s^3(\# \text{ of } \triangle\text{'s in }G)$, \\and 
\item $\# \text{ of disjoint }\triangle\text{'s} = s^2(\# \text{ of disjoint } \triangle\text{'s in }G)$.
\end{enumerate}


 So $$\text{dist}(G', \triangle\text{-freeness}) = \frac{\# \text{ disjoint }\triangle\text{'s}}{\binom m2} > \epsilon$$

(the last inequality simply follows from the choice of $m$ that we made). 


This implies $G'$ is $\epsilon$-far from $\triangle$-free. 
Plugging in  $s$, $m$ as functions of $\epsilon, n$ in item 3 above gives us that  $$\# \triangle\text{'s} < \Theta\left(\left(\frac \epsilon c\right)^{c \log{(c/\epsilon)}}\right)\binom{n}{3},$$ for some appropriately chosen $c$, as claimed in the theorem's statement.
 
\end{proof}

\bibliographystyle{plain}
\bibliography{biblio}
\end{document}
